package leetcode_day._2021._202109._0110;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/9 8:48
 * 文本左右对齐
 * 算法：字符串  模拟
 * 每个单词之间有一个空格
 * 如果一行有多个单词，那么最后一个单词一定要右对齐
 * 遍历 words，把能够满足一行的单词拿出来
 * 计算还有 n 个格子没有占用，将 n / 一行单词个数 得到 m
 * 这样每个单词 + m 个空格加入到 ans 后，n - m
 * --------------------------------------------------
 * 做了将近两个小时，思路很简单，就像上面说的
 * 之所以是困难，感觉是在空格分配这里把，也确实搞了好长时间
 * 当空格不能均匀分配时，要满足单词左边的空格大于右边的空格数
 * 每个将单词加入后，就要重新计算下一个单词所需的空格数
 */
public class _09_68 {
    public static void main(String[] args) {
        String[] words = {"ask", "not", "what", "your", "country", "can", "do", "for", "you", "ask", "what",
                "you", "can", "do", "for", "your", "country"};
        int maxWidth = 16;
        System.out.println(new _09_68().fullJustify_low(words, maxWidth));
    }

    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<>();
        int n = words.length;
        List<String> list = new ArrayList<>();
        for (int i = 0; i < n; ) {
            // list 装载当前行的所有 word
            list.clear();
            list.add(words[i]);
            int cur = words[i].length();
            int j = i + 1;
            while (j < n && cur + 1 + words[j].length() <= maxWidth) {
                cur += 1 + words[j].length();
                list.add(words[j++]);
            }
            i = j;

            // 当前行为最后一行，特殊处理为左对齐
            if (i == n) {
                StringBuilder sb = new StringBuilder(list.get(0));
                for (int k = 1; k < list.size(); k++) {
                    sb.append(" ").append(list.get(k));
                }
                while (sb.length() < maxWidth) sb.append(" ");
                ans.add(sb.toString());
                break;
            }

            // 如果当前行只有一个 word，特殊处理为左对齐
            int cnt = list.size();
            if (cnt == 1) {
                String str = list.get(0);
                while (str.length() != maxWidth) str += " ";
                ans.add(str);
                continue;
            }

            /**
             * 其余为一般情况
             * wordWidth : 当前行单词总长度;
             * spaceWidth : 当前行空格总长度;
             * spaceItem : 往下取整后的单位空格长度
             */
            int wordWidth = cur - (cnt - 1);
            int spaceWidth = maxWidth - wordWidth;
            int spaceItemWidth = spaceWidth / (cnt - 1);
            String spaceItem = "";
            for (int k = 0; k < spaceItemWidth; k++) spaceItem += " ";
            StringBuilder sb = new StringBuilder();
            for (int k = 0, sum = 0; k < cnt; k++) {
                String item = list.get(k);
                sb.append(item);
                if (k == cnt - 1) break;
                sb.append(spaceItem);
                sum += spaceItemWidth;
                // 剩余的间隙数量（可填入空格的次数）
                int remain = cnt - k - 1 - 1;
                // 剩余间隙数量 * 最小单位空格长度 + 当前空格长度 < 单词总长度，则在当前间隙多补充一个空格
                if (remain * spaceItemWidth + sum < spaceWidth) {
                    sb.append(" ");
                    sum++;
                }
            }
            ans.add(sb.toString());
        }
        return ans;
    }

    public List<String> fullJustify_low(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<>();
        int len = words.length;
        // curLen 表示一行单词的字符个数；curNum 表示一行单词的数量；curAdd 表示已经遍历的单词个数
        int curLen = 0, curNum = 0, curAdd = 0;
        for (int i = 0; i < len; ) {
            // 把之前单词的空格都算进去了
            if (curLen + curNum + words[i].length() > maxWidth) {
                // -- 之后的 curNum 表示现有单词之间的空格数量
                --curNum;
                // 空格数量
                int n = maxWidth - curLen;
                // 先给每个单词后面分配一个空格
                n -= curNum;
                // curNum 为 0，表示这一行只有一个单词，m 表示每个单词后可以分到的空格数量
                // n 为 0，表示空格已经被分配完了，每个单词后面必须跟一个空格，每一行（这行满了）的最后一个单词除外
                int m = curNum == 0 || n == 0 ? 0 : (int) Math.ceil(1.0 * n / curNum);
                StringBuilder res = new StringBuilder();
                for (int j = curAdd; j < i - 1; j++) {
                    res.append(words[j]).append(" ").append(getSpace(m));
                    ++curAdd;
                    --curNum;
                    n -= m;
                    // 重新分配空格数量
                    m = curNum == 0 ? 0 : (int) Math.ceil(n * 1.0 / curNum);
                }
                res.append(words[i - 1]).append(getSpace(maxWidth - res.length()));
                ++curAdd;
                ans.add(res.toString());
                curLen = curNum = 0;
            } else {
                curLen += words[i].length();
                ++curNum;
                ++i;
            }
        }
        StringBuilder res = new StringBuilder();
        for (; curAdd < len - 1; curAdd++) res.append(words[curAdd]).append(" ");
        res.append(words[len - 1]).append(getSpace(maxWidth - res.length()));
        ans.add(res.toString());
        return ans;
    }

    String getSpace(int num) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < num; i++) res.append(" ");
        return res.toString();
    }

}
